
class SplayDict(object):
	def __init__(self, iterable=None):
		self._root = None
		self._header = _SplayDictEntry(None, None, None, None)
		
		#
		# update with iterable
		#
		if isinstance(iterable, dict):
			for k, v in iterable.items():
				self[k] = v
		elif iterable:
			for k, v in iterable:
				self[k] = v
	
	def __setitem__(self, key, value):
		if self._root is None:
			self._root = _SplayDictEntry(key, value, None, None)
			return
		
		self.splay(key)
		
		if key == self._root.get_key():
			self._root.set_value(value)
			return
		
		n = _SplayDictEntry(key, value, None, None)
		
		if key < self._root.get_key():
			n.set_left(self._root.get_left())
			n.set_right(self._root)
			self._root.set_left(None)
		else:
			n.set_right(self._root.get_right())
			n.set_left(self._root)
			self._root.set_right(None)
		
		self._root = n
	
	def __getitem__(self, key):
		if self._root is None:
			raise KeyError('missing item')
		
		self.splay(key)
		
		if key != self._root.get_key():
			raise KeyError('missing item')
		
		return self._root.get_value()
	
	def __delitem__(self, key):
		if self._root is None:
			raise KeyError('missing item')
		
		self.splay(key)
		
		if key != self._root.get_key():
			raise KeyError('missing item')
		
		if self._root.get_left() is None:
			self._root = self._root.get_right()
		else:
			x = self._root.get_right()
			self._root = self._root.get_left()
			self.splay(key)
			self._root.set_right(x)
	
	def splay(self, key):
		t = self._root
		self._header.set_left(None)
		self._header.set_right(None)
		l = r = self._header
		
		while True:
			if key < t.get_key():
				if t.get_left() is None:
					break
				
				tl = t.get_left()
				
				if key < tl.get_key():
					y = t.get_left()
					t.set_left(y.get_right())
					y.set_right(t)
					t = y
					
					if t.get_left() is None:
						break
					
				r.set_left(t)
				r = t
				t = t.get_left()
			elif key > t.get_key():
				if t.get_right() is None:
					break
				
				tr = t.get_right()
				
				if key > tr.get_key():
					y = t.get_right()
					t.set_right(y.get_left())
					y.set_left(t)
					t = y
					
					if t.get_right() is None:
						break
				
				l.set_right(t)
				l = t
				t = t.get_right()
			else:
				break
		
		l.set_right(t.get_left())
		r.set_left(t.get_right())
		t.set_left(self._header.get_right())
		t.set_right(self._header.get_left())
		self._root = t

class _SplayDictEntry(object):
	def __init__(self, key, value, left, right):
		self._key = key
		self._value = value
		self._left = left
		self._right = right
	
	def set_key(self, key):
		self._key = key
	
	def get_key(self):
		return self._key
	
	def set_value(self, value):
		self._value = value
	
	def get_value(self):
		return self._value
	
	def set_left(self, left):
		self._left = left
	
	def get_left(self):
		return self._left
	
	def set_right(self, right):
		self._right = right
	
	def get_right(self):
		return self._right

def test1():
	t = SplayDict([('m', 't'), ('a', 'a'), ('r', 's'), ('k', 'i'), ('o', 'c')])
	
	print(t['r'])
	del t['r']
	
	try:
		print(t['r'])
	except KeyError:
		print('missing entry "%s"' % 'r')

def test2():
	t = SplayDict()
	
	for i in range(100000):
		k = str(i)
		v = str(100000 - i)
		t[k] = v
	
	for i in range(100000):
		k = str(i)
		v = t[k]

def test3():
	t = SplayDict()
	
	t['marko'] = 'tasic'
	t['milan'] = 'vasic'
	t['milos'] = 'prasic'
	
	print(t['marko'])
	t['marko'] = 'vasic'
	print(t['marko'])
	
	del t['marko']
	
	try: del t['marko']
	except KeyError: print('missing key to del')
	
	try: print(t['marko'])
	except KeyError: print('missing key to get')

def test4():
	import random
	
	t = SplayDict()
	d = {i:100000 for i in range(100000)}
	rkeys = d.keys()
	
	random.shuffle(rkeys)
	
	print('<')
	for k in rkeys:
		v = d[k]
		t[k] = v
	print('>')
	
	#~ random.shuffle(rkeys)
	
	#~ print('<')
	#~ k = random.randrange(0, 100000)
	#~ v = t[k]
	#~ print(k, v)
	#~ print('>')
	
	#~ random.shuffle(rkeys)
	
	#~ print('<')
	#~ for k in rkeys:
		#~ v = t[k]
	#~ print('>')
	
	#~ random.shuffle(rkeys)
	
	print('<')
	for k in rkeys:
		del t[k]
	print('>')

if __name__ == '__main__':
	test4()
